

class UnionFindSet:
    def __init__(self, n):
        self.father = [i for i in range(n)]
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        self.father[self.find(i)] = self.find(j)

class UnionFindSet2:
    def __init__(self, n):
        # 意思是1 ～ N， 0不算
        self.father = [i for i in range(n + 1)]
        self.size = [1] * (n + 1)
        self.n = n

    def find(self, i):
        # 查询一个节点的根节点
        # while self.father[i] != i:
        #   i = self.father[i]
        # return i
        # 【扁平化】：在这个过程中，将这一路都直接指向根
        # stack = []
        # while self.father[i] != i:
        #     stack.append(i)
        #     i = self.father[i]
        # while stack:
        #     self.father[stack.pop()] = i
        # return i
        if i != self.father[i]:
            self.father[i] = self.find(self.father[i])
        return self.father[i]

    def union(self, a, b):
        # 【小挂大】：小集合去挂大集合
        i, j = self.find(a), self.find(b)
        if i == j:
            return
        if self.size[i] <= self.size[j]:
            self.father[i] = j
            self.size[j] += self.size[i]
        else:
            self.father[j] = i
            self.size[i] += self.size[j]

    def is_same_set(self,a, b):
        return self.find(a) == self.find(b)

class UnionFindSet3:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.size = [1] * n

    def find(self, i):
        if i != self.father[i]:
            self.father[i] = self.find(self.father[i])
        return self.father[i]

    def union(self, a, b):
        i, j = self.find(a), self.find(b)
        if i == j:
            return
        if self.size[i] <= self.size[j]:
            self.father[i] = j
            self.size[j] += self.size[i]
        else:
            self.father[j] = i
            self.size[i] += self.size[j]

    def is_same_set(self,a, b):
        return self.find(a) == self.find(b)



class UnionFindSet4:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        x, y = self.find(i), self.find(j)
        if x != y:
            self.father[x] = y
            self.sets -= 1
